Scheduling directives: Accelerating shared-memory many-core processor execution

We consider many-core processors with a task-graph oriented programming model, whereby scheduling constraints among tasks are decided offline, and are then enforced by the runtime system using dedicated hardware. Here, exposing and beneficially exploiting fine grain data and control parallelism is increasingly important. Therefore, high expressive power for stating such constraints/directives, along with the ability to implement them in fast, simple hardware, is critical for success. In this paper, we focus on the relationship among different duplicable (multi-instance) tasks, which are used to express and exploit data parallelism. We extend the conventional Start-After-Complete (precedence) constraint to also be usable between replicas of different such tasks rather than only between entire tasks, thereby increasing the exposable parallelism. Additionally, we propose the parameterized Start-After-Start constraint, which can be used to control the degree of “lockstep” among multiple such tasks, e.g., in order to improve cache performance when the tasks work on the same data. Also, we briefly describe several additional interesting directives. Finally, we show that the directives can be supported efficiently in hardware. Hypercore, a very efficient CREW PRAM-like shared-cache architecture, which is very challenging because it has extremely fast dispatching for basic constraints, is used in the discussion. However, the new directives have broader applicability. Having shown the possibility of simple implementation and indications of benefit, this motivates further exploration of these directives and their implementation in hardware, as well as their support by programming tools.     

On multigrid-CG for efficient topology optimization

This article presents a computational approach that facilitates the efficient solution of 3-D structural topology optimization problems on a standard PC. Computing time associated with solving the nested analysis problem is reduced significantly in comparison to other existing approaches. The cost reduction is obtained by exploiting specific characteristics of a multigrid preconditioned conjugate gradients (MGCG) solver. In particular, the number of MGCG iterations is reduced by relating it to the geometric parameters of the problem. At the same time, accurate outcome of the optimization process is ensured by linking the required accuracy of the design sensitivities to the progress of optimization. The applicability of the proposed procedure is demonstrated on several 2-D and 3-D examples involving up to hundreds of thousands of degrees of freedom. Implemented in MATLAB, the MGCG-based program solves 3-D topology optimization problems in a matter of minutes. This paves the way for efficient implementations in computational environments that do not enjoy the benefits of high performance computing, such as applications on mobile devices and plug-ins for modeling software.     

On-line restricted assignment of temporary tasks with unknown durations

We consider load balancing of temporary tasks on m machines in the restricted assignment model. It is known that the best competitive ratio for this problem is . This bound is not achieved by the greedy algorithm whose competitive ratio is known to be Ω(m2/3). We give an alternative analysis to the greedy algorithm which is better than the known analysis for relatively small values of m. We also show that for a small number of machines, namely m?5, the greedy algorithm is optimal.     

The tensor product of two good codes is not necessarily robustly testable

Given two codes R and C, their tensor product $R?C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R?C$ is said to be robust if for every matrix M that is far from $R?C$ it holds that the rows and columns of M are far on average from R and C respectively. Ben-Sasson and Sudan (RSA 28(4), 2006) have asked under which conditions the product $R?C$ is robust.Addressing this question, Paul Valiant (APPROX-RANDOM 2005) constructed two linear codes with constant relative distance whose tensor product is not robust. However, one of those codes has a sub-constant rate. We show that this construction can be modified such that both codes have both constant rate and constant relative distance. We also provide an alternative proof for the non-robustness of the tensor product of those codes, based on the inverse direction of the “rectangle method” that was presented by the second author (ECCC TR07-061). We believe that this proof gives an additional intuition for why this construction works.     

How to construct constant-round zero-knowledge proof systems for NP

Constant-round zero-knowledge proof systems for every language in are presented, assuming the existence of a collection of claw-free functions. In particular, it follows that such proof systems exist assuming the intractability of either the Discrete Logarithm Problem or the Factoring Problem for Blum integers.     

13C-MRS studies on cerebral metabolism

¹³C from labeled glucose is normally incorporated rapidly into cerebral glutamate with little detectable glutamine or citrate. In contrast, glutamine and citrate only show significant labeling from¹³C acetate, which reflects metabolism in glial cells. When brain slices are depolarized with 40 mM KC1 (which mirrors some of the conditions of epilepsy) the¹³C enrichment of glutamine and citrate from glucose is accelerated in contrast to that of glutamate, which is not. This clearly indicates that depolarizing conditions stimulate glial rather than neuronal consumption of glucose.In tissues subjected to hypoxia, there is greatly increased labeling of glycerol 3-phosphate, which was confirmed by its increased presence in³¹P-MR (magnetic resonance) spectra. Analysis of the labeling of lactate, alanine, and glycerol 3-phosphate demonstrated that the ability of the brain to maintain normal function in hypoxia is limited by the capacity of the key enzyme, lactate dehydrogenase. This has implications in the clinical assessment and management of stroke. These results also have implications in the interpretation of activation studies, where increased lactate could be due either to depolarization or hypoxia, or both.The spectra observed in studies on metabolism of U-[¹³C] glutamate in cerebral preparations revealed clear signals from glutamine and lactate released to the media. The isotopomer patterns of the lactate showed that it must have arisen from the exogenous glutamate, because if it were due to naturally abundant¹³C in the lactate, only singlets would have appeared. Comparison of the isotopomer patterns and the percentage¹³C enrichments of the glutamine and lactate showed that there is higher incorporation of¹³C from exogenous glutamate into lactate than into glutamine. The enrichment of the lactate indicated that very little was derived from glucose and suggests that the glutamate is converted to lactate in the glia for use by the neurones.     

Preconditioning of AISI 304 stainless steel surfaces in the presence of flavins—Part I: Effect on surface chemistry and corrosion behavior

Stainless steel AISI 304 surfaces were studied after a mild anodic polarization for oxide growth in the presence and absence of two derivatives of vitamin B2 (riboflavin and flavin mononucleotide) that can be secreted by metal-reducing bacteria and act as a chelating agent for iron species. The alterations in oxide chemistry were studied by means of surface-sensitive techniques such as X-ray photoelectron spectroscopy and time-of-flight secondary ion mass spectrometry analysis. The complementary electrochemical characterization revealed a preferential growth of an oxide/hydroxide iron-rich film that is responsible for an altered pit initiation and nucleation behavior. These findings suggest that as the corrosion behavior is determined by the interplay of the chemical and electronic properties, only a mild anodic polarization in the presence of redox-active molecules is able to alter the chemical and electronic structure of the passive film formed on stainless steel AISI 304. This helps to achieve a profound understanding of the mechanisms of microbially influenced corrosion (MIC) and especially the possible effects of the redox-active biomolecules, as they may play an important role in the corrosion susceptibility of stainless steel surfaces.     

Nonlinear Analysis of Masonry Arches Strengthened with Composite Materials

The nonlinear behavior of masonry arches strengthened with externally bonded composite materials is investigated. A finite-element (FE) formulation that is specially tailored for the nonlinear analysis of the strengthened arch is developed. The FE formulation takes into account material nonlinearity of the masonry construction and high-order kinematic relations for the layered element. Implementation of the above concept in the FE framework reduces the general problem to a one-dimensional nonlinear formulation in polar coordinates with a closed-form representation of the elemental Jacobian matrix (tangent stiffness). A numerical study that examines the capabilities of the model and highlights various aspects of the nonlinear behavior of the strengthened masonry arch is presented. Emphasis is placed on the unique effects near irregular points and the nonlinear evolution of these effects through the loading process. A comparison with experimental results and a discussion of the correlating aspects and the ones that designate needs of further study are also presented.     

Approximate reanalysis in topology optimization

In the nested approach to structural optimization, most of the computational effort is invested in the solution of finite element analysis equations. In this study, the integration of an approximate reanalysis procedure into the framework of topology optimization of continuum structures is investigated. The nested optimization problem is reformulated to accommodate the use of an approximate displacement vector and the design sensitivities are derived accordingly. It is shown that relatively rough approximations are acceptable since the errors are taken into account in the sensitivity analysis. The implementation is tested on several small and medium scale problems, including 2‐D and 3‐D minimum compliance problems and 2‐D compliant force inverter problems. Accurate results are obtained and the savings in computation time are promising. Copyright © 2008 John Wiley & Sons, Ltd.     

Structural behavior and inter-layer displacements in CFRP plated steel beams – Optical measurements,analysis, and comparative verification

The linear elastic structural behavior of steel beams strengthened with externally bonded composite materials is experimentally and analytically investigated. The paper focuses on the full-field inter-layer relative displacements between the beam and the FRP layer. Such displacements result from the interaction between the adhesively bonded components and it is the integrated outcome of the interfacial conditions and the deformability of the adhesive. As such, it is commonly adopted as the state variable in simplified bond shear stress–slip representations. This aspect, as well as other aspects of the global and localized structural response, is analytically and experimentally quantified. The experiment includes a simply supported steel beam strengthened with a CFRP plate. A 3D image correlation technique with sequential measurements is used for the assessment of the full-field inter-layer displacements along the beam. The analysis adopts a high order modeling approach that accounts for the 2D stress and displacement fields through the depth of the adhesive and a 1D shear stress–slip approach using only a linear increasing branch. The comparison between the results provides validation of the analytical and experimental capabilities with emphasis on the inter-layer effects. One of the interesting findings which is discussed and explained in this paper is the fact that the slip values calculated with the shear stress–slip approach are notably different from the ones that can be measured experimentally and determined by the high order model.